% LaTeX source for textbook ``How to think like a computer scientist''
% Copyright (c)  2001  Allen B. Downey, Jeffrey Elkner, and Chris Meyers.

% Permission is granted to copy, distribute and/or modify this
% document under the terms of the GNU Free Documentation License,
% Version 1.1  or any later version published by the Free Software
% Foundation; with the Invariant Sections being "Contributor List",
% with no Front-Cover Texts, and with no Back-Cover Texts. A copy of
% the license is included in the section entitled "GNU Free
% Documentation License".

% This distribution includes a file named fdl.tex that contains the text
% of the GNU Free Documentation License.  If it is missing, you can obtain
% it from www.gnu.org or by writing to the Free Software Foundation,
% Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
%

\chapter{Trees}
\index{tree}
\index{node}
\index{tree node}
\index{cargo}
\index{embedded reference}
\index{binary tree}

Like linked lists, trees are made up of nodes.  A common kind of tree
is a {\bf binary tree}, in which each node contains a reference to two
other nodes (possibly null).  These references are referred to as the
left and right subtrees.  Like list nodes, tree nodes also contain
cargo.  A state diagram for a tree looks like this:

\label{tree}
\beforefig
\centerline{\psfig{figure=illustrations/tree1.eps,height=1.7in}}
\afterfig

To avoid cluttering up the picture, we often omit the
{\tt Nones}.

The top of the tree (the node {\tt tree} refers to) is called the
{\bf root}.  In keeping with the tree metaphor, the other nodes are
called branches and the nodes at the tips with null references are
called {\bf leaves}.  It may seem odd that we draw the picture with
the root at the top and the leaves at the bottom, but that is not the
strangest thing.

\index{root node}
\index{leaf node}
\index{parent node}
\index{child node}
\index{level}

To make things worse, computer scientists mix in another
metaphor---the family tree.  The top node is sometimes called
a {\bf parent} and the nodes it refers to are its {\bf children}.
Nodes with the same parent are called {\bf siblings}.

Finally, there is a geometric vocabulary for talking
about trees.  We already mentioned left and right, but there is
also ``up'' (toward the parent/root) and ``down'' (toward the
children/leaves).  Also, all of the nodes that are the same
distance from the root comprise a {\bf level} of the tree.

We probably don't need three metaphors for talking about trees,
but there they are.

Like linked lists, trees are recursive data structures because
they are defined recursively.

\index{recursive data structure}
\index{data structure!recursive}

\begin{quote}
A tree is either:

\begin{itemize}

\item the empty tree, represented by {\tt None}, or

\item a node that contains an object reference and two
tree references.

\end{itemize}

\end{quote}

\index{tree!empty}


\section {Building trees}

The process of assembling a tree is similar
to the process of assembling a linked list.
Each constructor invocation builds a single node.

\beforeverb
\begin{verbatim}
class Tree:
  def __init__(self, cargo, left=None, right=None):
    self.cargo = cargo
    self.left  = left
    self.right = right

  def __str__(self):
    return str(self.cargo)
\end{verbatim}
\afterverb
%
The {\tt cargo} can
be any type, but the arguments for {\tt left} and {\tt right} should be
tree nodes.  {\tt left} and {\tt right} are optional; the default
value is {\tt None}.

To print a node, we just print the cargo.

One way to build a tree is from the bottom up.
Allocate the child nodes first:

\beforeverb
\begin{verbatim}
left = Tree(2)
right = Tree(3)
\end{verbatim}
\afterverb
%
Then create the parent node and link it to the children:

\beforeverb
\begin{verbatim}
tree = Tree(1, left, right);
\end{verbatim}
\afterverb
%
We can write this code more concisely by nesting constructor
invocations:

\beforeverb
\begin{verbatim}
>>> tree = Tree(1, Tree(2), Tree(3))
\end{verbatim}
\afterverb
%
Either way, the result is the tree at the beginning of the
chapter.


\section {Traversing trees}
\index{tree!traversal}
\index{traverse}
\index{recursion}

Any time you see a new data structure, your first
question should be, ``How do I traverse it?''  The most natural
way to traverse a tree is recursively.  For example, if the
tree contains integers as cargo, this function returns their sum:

\beforeverb
\begin{verbatim}
def total(tree):
  if tree == None: return 0
  return total(tree.left) + total(tree.right) + tree.cargo
\end{verbatim}
\afterverb
%
The base case is the empty tree, which contains no cargo, so
the sum is 0.
The recursive step
makes two recursive calls to find the sum of the child trees.
When the recursive calls complete,
we add the cargo of the parent and return the
total.


\section {Expression trees}
\index{tree!expression}
\index{expression tree}
\index{postfix}
\index{infix}
\index{binary operator}
\index{operator!binary}

A tree is a natural way to represent the structure of an expression.
Unlike other notations, it can represent the computation
unambiguously.  For example, the infix expression {\tt 1 + 2 * 3} is
ambiguous unless we know that the multiplication happens before the
addition.

This expression tree represents the same computation:

\beforefig
\centerline{\psfig{figure=illustrations/tree2.eps,height=2in}}
\afterfig

The nodes of an expression tree can be operands like {\tt 1} and
{\tt 2} or operators like {\tt +} and {\tt *}.  Operands are leaf nodes;
operator nodes contain references to their operands.  (All of these
operators are {\bf binary}, meaning they have exactly two operands.)

We can build this tree like this:

\beforeverb
\begin{verbatim}
>>> tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))
\end{verbatim}
\afterverb
%
Looking at the figure, there is no question what the order of
operations is; the multiplication happens first in order to compute
the second operand of the addition.

Expression trees have many uses.  The example in this chapter uses
trees to translate expressions to postfix, prefix, and infix.
Similar trees are used inside compilers to parse, optimize, and
translate programs.


\section {Tree traversal}
\index{tree!traversal}
\index{traverse}
\index{recursion}
\index{preorder}
\index{postorder}
\index{inorder}

We can traverse an expression tree and print the contents like this:

\beforeverb
\begin{verbatim}
def printTree(tree):
  if tree == None: return
  print tree.cargo,
  printTree(tree.left)
  printTree(tree.right)
\end{verbatim}
\afterverb
%
\index{preorder}
\index{prefix}

In other words, to print a tree, first print the contents of
the root, then print the entire left subtree, and then print the
entire right subtree.  This way of traversing a tree is called
a {\bf preorder}, because the contents of the root appear {\em before}
the contents of the children.
For the previous example, the output is:

\beforeverb
\begin{verbatim}
>>> tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))
>>> printTree(tree)
+ 1 * 2 3
\end{verbatim}
\afterverb
%
This format is different from both postfix and infix; it is another
notation called {\bf prefix}, in which the operators appear before
their operands.

You might suspect that if you traverse the tree in a
different order, you will get the expression in a different
notation.  For example, if you print the subtrees first and then
the root node, you get:

\beforeverb
\begin{verbatim}
def printTreePostorder(tree):
  if tree == None: return
  printTreePostorder(tree.left)
  printTreePostorder(tree.right)
  print tree.cargo,
\end{verbatim}
\afterverb
%
\index{postorder}
\index{inorder}
The result, {\tt 1 2 3 * +}, is in postfix!
This order of traversal is called {\bf postorder}.

Finally, to traverse a tree {\bf inorder},
you print the left tree, then the root, and then the right tree:

\beforeverb
\begin{verbatim}
def printTreeInorder(tree):
  if tree == None: return
  printTreeInorder(tree.left)
  print tree.cargo,
  printTreeInorder(tree.right)
\end{verbatim}
\afterverb
%
The result is {\tt 1 + 2 * 3}, which is the expression in infix.

To be fair, we should point out that we have omitted an
important complication.  Sometimes when we write an expression
in infix, we have to use parentheses to preserve the order of
operations.  So an inorder traversal is not quite sufficient to
generate an infix expression.

Nevertheless, with a few improvements, the expression tree and the
three recursive traversals provide a general way to translate
expressions from one format to another.

\begin{quote}
{\em As an exercise, modify {\tt printTreeInorder} so that it
puts parentheses around every operator and pair of operands.
Is the output correct and unambiguous?  Are the parentheses
always necessary? }
\end{quote}

If we do an inorder traversal and keep track of what level
in the tree we are on, we can generate a graphical representation
of a tree:

\beforeverb
\begin{verbatim}
def printTreeIndented(tree, level=0):
  if tree == None: return
  printTreeIndented(tree.right, level+1)
  print '  '*level + str(tree.cargo)
  printTreeIndented(tree.left, level+1)
\end{verbatim}
\afterverb
%
The parameter {\tt level} keeps track of where we are in the
tree.  By default, it is initially 0.  Each time we make a
recursive call, we pass {\tt level+1} because the child's level
is always one greater than the parent's.  Each item is indented by
two spaces per level.  The result for the example tree is:

\beforeverb
\begin{verbatim}
>>> printTreeIndented(tree)
    3
  *
    2
+
  1
\end{verbatim}
\afterverb
%
If you look at the output sideways, you see a simplified version
of the original figure.



\section{Building an expression tree}
\index{expression tree}
\index{tree!expression}
\index{parse}
\index{token}

In this section, we parse infix expressions and build the
corresponding expression trees.  For example, the expression
{\tt (3+7)*9} yields the following tree:

\beforefig
\centerline{\psfig{figure=illustrations/tree3.eps}}
\afterfig

Notice that we have simplified the diagram by leaving
out the names of the attributes.

The parser we will write handles expressions that include numbers,
parentheses, and the operators {\tt +} and {\tt *}.
We assume that the input string has already
been tokenized into a Python list.  The token list for
{\tt (3+7)*9} is:

\beforeverb
\begin{verbatim}
['(', 3, '+', 7, ')', '*', 9, 'end']
\end{verbatim}
\afterverb
%
The {\tt end} token is useful for preventing the parser from
reading past the end of the list.

\begin{quote}
{\em As an exercise, write a function that takes an expression
string and returns a token list.}
\end{quote}

The first function we'll write is {\tt getToken}, which takes a token
list and an expected token as arguments.  It compares the expected
token to the first token on the list: if they match, it removes the
token from the list and returns true; otherwise, it returns false:

\beforeverb
\begin{verbatim}
def getToken(tokenList, expected):
  if tokenList[0] == expected:
    del tokenList[0]
    return True
  else:
    return False
\end{verbatim}
\afterverb
%
Since {\tt tokenList} refers to a mutable object, the changes made
here are visible to any other variable that refers to the same object.

The next function, {\tt getNumber}, handles operands.
If the next token in {\tt tokenList} is a number,
{\tt getNumber} removes it and returns a leaf node containing
the number; otherwise, it returns {\tt None}.

\beforeverb
\begin{verbatim}
def getNumber(tokenList):
  x = tokenList[0]
  if not isinstance(x, int): return None
  del tokenList[0]
  return Tree (x, None, None)
\end{verbatim}
\afterverb
%
Before continuing, we should test {\tt getNumber} in isolation.  We
assign a list of numbers to {\tt tokenList}, extract the first,
print the result, and print what remains of the token list:

\beforeverb
\begin{verbatim}
>>> tokenList = [9, 11, 'end']
>>> x = getNumber(tokenList)
>>> printTreePostorder(x)
9
>>> print tokenList
[11, 'end']
\end{verbatim}
\afterverb
%
The next method we need is {\tt getProduct}, which builds an
expression tree for products.  A simple product has two numbers as
operands, like {\tt 3 * 7}.

Here is a version of {\tt getProduct} that handles
simple products.

\beforeverb
\begin{verbatim}
def getProduct(tokenList):
  a = getNumber(tokenList)
  if getToken(tokenList, '*'):
    b = getNumber(tokenList)
    return Tree ('*', a, b)
  else:
    return a
\end{verbatim}
\afterverb
%
Assuming that {\tt getNumber} succeeds and returns a singleton tree,
we assign the first operand to {\tt a}.
If the next character is {\tt *}, we get the second number
and build an expression tree with {\tt a}, {\tt b},
and the operator.

If the next character is anything else, then we just return
the leaf node with {\tt a}.  Here are two examples:

\beforeverb
\begin{verbatim}
>>> tokenList = [9, '*', 11, 'end']
>>> tree = getProduct(tokenList)
>>> printTreePostorder(tree)
9 11 *
\end{verbatim}
\afterverb

\beforeverb
\begin{verbatim}
>>> tokenList = [9, '+', 11, 'end']
>>> tree = getProduct(tokenList)
>>> printTreePostorder(tree)
9
\end{verbatim}
\afterverb
%
The second example implies that we consider a single
operand to be a kind of product.  This definition of
``product'' is counterintuitive, but it turns out to
be useful.  

Now we have to deal with compound products, like like {\tt 3 * 5 *
13}.  We treat this expression as a product of products, namely {\tt 3
* (5 * 13)}.  The resulting tree is:

\beforefig
\centerline{\psfig{figure=illustrations/tree4.eps}}
\afterfig

With a small change in {\tt getProduct}, we can handle
an arbitrarily long product:

\beforeverb
\begin{verbatim}
def getProduct(tokenList):
  a = getNumber(tokenList)
  if getToken(tokenList, '*'):
    b = getProduct(tokenList)       # this line changed
    return Tree ('*', a, b)
  else:
    return a
\end{verbatim}
\afterverb
%
In other words, a product can be either a singleton or a tree with
{\tt *} at the root, a number on the left, and a product on the right.
This kind of recursive definition should be starting to feel
familiar.

\index{product}
\index{definition!recursive}
\index{recursive definition}

Let's test the new version with a compound product:

\beforeverb
\begin{verbatim}
>>> tokenList = [2, '*', 3, '*', 5 , '*', 7, 'end']
>>> tree = getProduct(tokenList)
>>> printTreePostorder(tree)
2 3 5 7 * * *
\end{verbatim}
\afterverb
%
Next we will add the ability to parse sums.  Again, we
use a slightly counterintuitive definition of ``sum.''
For us, a sum can be a tree with {\tt +} at the root,
a product on the left, and a sum on the right.  Or, a sum
can be just a product.

\index{sum}

If you are willing to play along with this definition, it has a nice
property: we can represent any expression (without parentheses) as a
sum of products.  This property is the basis of our parsing algorithm.

{\tt getSum} tries to build a tree with a product on the left and a
sum on the right.  But if it doesn't find a {\tt +}, it just builds a
product.

\beforeverb
\begin{verbatim}
def getSum(tokenList):
  a = getProduct(tokenList)
  if getToken(tokenList, '+'):
    b = getSum(tokenList)
    return Tree ('+', a, b)
  else:
    return a
\end{verbatim}
\afterverb
%
Let's test it with {\tt 9 * 11 + 5 * 7}:

\beforeverb
\begin{verbatim}
>>> tokenList = [9, '*', 11, '+', 5, '*', 7, 'end']
>>> tree = getSum(tokenList)
>>> printTreePostorder(tree)
9 11 * 5 7 * +
\end{verbatim}
\afterverb
%
We are almost done, but we still have to handle parentheses.
Anywhere in an expression where there can be a number, there can
also be an entire sum
enclosed in parentheses.  We just need to modify {\tt getNumber} to
handle {\bf subexpressions}:

\index{subexpression}

\beforeverb
\begin{verbatim}
def getNumber(tokenList):
  if getToken(tokenList, '('):
    x = getSum(tokenList)         # get the subexpression
    getToken(tokenList, ')')      # remove the closing parenthesis
    return x
  else:
    x = tokenList[0]
    if not isinstance(x, int): return None
    tokenList[0:1] = []
    return Tree (x, None, None)    
\end{verbatim}
\afterverb
%
Let's test this code with {\tt 9 * (11 + 5) * 7}:

\beforeverb
\begin{verbatim}
>>> tokenList = [9, '*', '(', 11, '+', 5, ')', '*', 7, 'end']
>>> tree = getSum(tokenList)
>>> printTreePostorder(tree)
9 11 5 + 7 * *
\end{verbatim}
\afterverb
%
\adjustpage{-2}
\pagebreak

The parser handled the parentheses correctly; the addition happens
before the multiplication.

In the final version of the program, it would be a good idea
to give {\tt getNumber} a name
more descriptive of its new role.


\section{Handling errors}
\index{handling errors}
\index{error handling}

Throughout the parser, we've been assuming that expressions are
well-formed.  For example, when we reach the end of a
subexpression, we assume that the next character is a close
parenthesis.  If there is an error and the next character is something
else, we should deal with it.

\beforeverb
\begin{verbatim}
def getNumber(tokenList):
  if getToken(tokenList, '('):
    x = getSum(tokenList)       
    if not getToken(tokenList, ')'):
      raise ValueError, 'missing parenthesis'
    return x
  else:
    # the rest of the function omitted
\end{verbatim}
\afterverb
%
The {\tt raise} statement creates an exception; in this
case a {\tt ValueError}.  If the function that called
{\tt getNumber}, or one of the other functions in the
traceback, handles the exception, then the program
can continue.  Otherwise, Python will print an error message
and quit.

\begin{quote}
{\em As an exercise, find other places in these functions where errors
can occur and add appropriate {\tt raise} statements.
Test your code with improperly
formed expressions.}
\end{quote}


\section{The animal tree}
\index{animal game}
\index{game!animal}
\index{knowledge base}

In this section, we develop a small program that uses a tree
to represent a knowledge base.

The program interacts with the user to create a tree of questions
and animal names.  Here is a sample run:

\adjustpage{-3}
\pagebreak

\beforeverb
\begin{verbatim}
Are you thinking of an animal? y
Is it a bird? n
What is the animals name? dog
What question would distinguish a dog from a bird? Can it fly
If the animal were dog the answer would be? n

Are you thinking of an animal? y
Can it fly? n
Is it a dog? n
What is the animals name? cat
What question would distinguish a cat from a dog? Does it bark
If the animal were cat the answer would be? n

Are you thinking of an animal? y
Can it fly? n
Does it bark? y
Is it a dog? y
I rule!

Are you thinking of an animal? n
\end{verbatim}
\afterverb
%
Here is the tree this dialog builds:

\beforefig
\centerline{\psfig{figure=illustrations/tree5.eps}}
\afterfig

At the beginning of each round, the program starts at the top of the
tree and asks the first question.  Depending on the answer, it moves
to the left or right child and continues until it gets to a leaf
node.  At that point, it makes a guess.  If the guess is not correct,
it asks the user for the name of the new animal and a question that
distinguishes the (bad) guess from the new animal.  Then it adds a
node to the tree with the new question and the new animal.

Here is the code:

\adjustpage{-2}
\pagebreak

\beforeverb
\begin{verbatim}
def animal():
  # start with a singleton
  root = Tree("bird")

  # loop until the user quits
  while True:
    print
    if not yes("Are you thinking of an animal? "): break

    # walk the tree
    tree = root
    while tree.getLeft() != None:
      prompt = tree.getCargo() + "? "
      if yes(prompt):
        tree = tree.getRight()
      else:
        tree = tree.getLeft()

    # make a guess
    guess = tree.getCargo()
    prompt = "Is it a " + guess + "? "
    if yes(prompt):
      print "I rule!"
      continue

    # get new information
    prompt  = "What is the animal's name? "
    animal  = raw_input(prompt)
    prompt  = "What question would distinguish a %s from a %s? "
    question = raw_input(prompt % (animal,guess))

    # add new information to the tree
    tree.setCargo(question)
    prompt = "If the animal were %s the answer would be? "
    if yes(prompt % animal):
      tree.setLeft(Tree(guess))
      tree.setRight(Tree(animal))
    else:
      tree.setLeft(Tree(animal))
      tree.setRight(Tree(guess))
\end{verbatim}
\afterverb
%
The function {\tt yes} is a helper; it prints a prompt and then
takes input from the user.  If the response
begins with {\em y} or {\em Y}, the function returns true:

\beforeverb
\begin{verbatim}
def yes(ques):
  from string import lower
  ans = lower(raw_input(ques))
  return (ans[0] == 'y')
\end{verbatim}
\afterverb
%
The condition of the outer loop is {\tt True}, which means it will
continue until the {\tt break} statement executes, if the user
is not thinking of an animal.

The inner {\tt while} loop walks the tree from top to bottom,
guided by the user's responses.

When a new node is added to the tree, the new question replaces
the cargo, and the two children are the new animal and the original
cargo.

One shortcoming of the program is that when it exits, it forgets
everything you carefully taught it!

\begin{quote}
{\em As an exercise, think of various ways you might save
the knowledge tree in a file.  Implement the one you think
is easiest.}
\end{quote}


\section{Glossary}
\index{binary tree}
\index{node}
\index{root node}
\index{leaf node}
\index{parent node}
\index{child node}
\index{sibling node}
\index{level}
\index{prefix}
\index{preorder}
\index{postorder}
\index{inorder}
\index{binary operator}
\index{operator!binary}

\begin{description}

\item[binary tree:]  A tree in which each node refers to zero, one, or
two dependent nodes.

\item[root:]  The topmost node in a tree, with no parent.

\item[leaf:]  A bottom-most node in a tree, with no children.

\item[parent:]  The node that refers to a given node.

\item[child:]  One of the nodes referred to by a node.

\item[siblings:]  Nodes that share a common parent.

\item[level:]  The set of nodes equidistant from the root.

\item[binary operator:]  An operator that takes two operands.

\item[subexpression:]  An expression in parentheses that acts
as a single operand in a larger expression.

\item[preorder:]  A way to traverse a tree, visiting each node
before its children.

\item[prefix notation:]  A way of writing a mathematical expression
with each operator appearing before its operands.

\item[postorder:]  A way to traverse a tree, visiting the children
of each node before the node itself.

\item[inorder:]  A way to traverse a tree, visiting the left subtree,
then the root, and then the right subtree.

\end{description}






